Search Results

Documents authored by Zeng, Ji

Document
DOI: 10.4230/LIPIcs.SoCG.2023.59
On Higher Dimensional Point Sets in General Position

Authors: Andrew Suk and Ji Zeng

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
A finite point set in ℝ^d is in general position if no d + 1 points lie on a common hyperplane. Let α_d(N) be the largest integer such that any set of N points in ℝ^d with no d + 2 members on a common hyperplane, contains a subset of size α_d(N) in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that α₂(N) < N^{5/6 + o(1)}. In this paper, we also use the container method to obtain new upper bounds for α_d(N) when d ≥ 3. More precisely, we show that if d is odd, then α_d(N) < N^{1/2 + 1/(2d) + o(1)}, and if d is even, we have α_d(N) < N^{1/2 + 1/(d-1) + o(1)}. We also study the classical problem of determining the maximum number a(d,k,n) of points selected from the grid [n]^d such that no k + 2 members lie on a k-flat. For fixed d and k, we show that a(d,k,n)≤ O(n^{d/{2⌊(k+2)/4⌋}(1- 1/{2⌊(k+2)/4⌋d+1})}), which improves the previously best known bound of O(n^{d/⌊(k + 2)/2⌋}) due to Lefmann when k+2 is congruent to 0 or 1 mod 4.
Cite as

Andrew Suk and Ji Zeng. On Higher Dimensional Point Sets in General Position. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2023.59,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{On Higher Dimensional Point Sets in General Position}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{59:1--59:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.59},
  URN =		{urn:nbn:de:0030-drops-179097},
  doi =		{10.4230/LIPIcs.SoCG.2023.59},
  annote =	{Keywords: independent sets, hypergraph container method, generalised Sidon sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.62
A Positive Fraction Erdős-Szekeres Theorem and Its Applications

Authors: Andrew Suk and Ji Zeng

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A famous theorem of Erdős and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least √n. Here, we prove a positive fraction version of this theorem. For n > (k-1)², any sequence A of n distinct real numbers contains a collection of subsets A_1,…, A_k ⊂ A, appearing sequentially, all of size s = Ω(n/k²), such that every subsequence (a_1,…, a_k), with a_i ∈ A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1,…, A_k) described above is called block-monotone of depth k and block-size s. Our theorem is asymptotically best possible and follows from a more general Ramsey-type result for monotone paths, which we find of independent interest. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k²log k) block-monotone subsequences of depth at least k, upon deleting at most (k-1)² entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.
Cite as

Andrew Suk and Ji Zeng. A Positive Fraction Erdős-Szekeres Theorem and Its Applications. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 62:1-62:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{suk_et_al:LIPIcs.SoCG.2022.62,
  author =	{Suk, Andrew and Zeng, Ji},
  title =	{{A Positive Fraction Erd\H{o}s-Szekeres Theorem and Its Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{62:1--62:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.62},
  URN =		{urn:nbn:de:0030-drops-160703},
  doi =		{10.4230/LIPIcs.SoCG.2022.62},
  annote =	{Keywords: Erd\H{o}s-Szekeres, block-monotone, monotone biarc diagrams, mutually avoiding sets}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact